\chapter{Bootstrapping}

\section{Objectives and principles}

\sysname{} is created from a fairly large number of external
libraries.  Some of these libraries were originally written as modules
of \sysname{}, but some were not.  Many of those libraries use a large
number of features of the \commonlisp{} language, including features
of \clos{} such as the possibility of creating generic functions,
classes, and even new method combinations.  For that reason, we must
provide a bootstrapping procedure that can handle pretty much
arbitrary \commonlisp{} code.  In particular, we cannot do what many
existing \commonlisp{} implementations do, namely load \clos{} late in
the bootstrapping process.

Furthermore, the \sysname{} bootstrapping procedure aims to improve on
the way the main existing \clos{} implementation (Portable Common
Loops, or PCL) and its derivatives work.  Specifically, PCL avoids
metastability issues by special-casing certain situations as
documented in appendix C of the book ``the Art of the Metaobject
Protocol'' \cite{Kiczales:1991:AMP:574212}.  We do that by applying
the techniques documented in two of our articles
(\cite{Strandh:2014:RMI:2635648.2635656}, \cite{durand:hal-02417646}).

Essentially, we make sure important slot accessors operate by
accessing the standard object by index directly, rather than by going
through \texttt{slot-value}.  As a result, the example of
\texttt{class-slots} in appendix C of the book is not a problem in
\sysname{}, because it never needs to call \texttt{slot-value}.  But
to accomplish this direct access, at some point, the slot metaobject
had to be accessed so that the index of the slot in the instance could
be determined.  We accomplish this possibility by calling a
preexisting version of \texttt{class-slots}.  This recursion
terminates by a version of \texttt{class-slots} that we define as a
generic function in the host \commonlisp{} system used for
bootstrapping, and so it is already operational.

\section{General technique}

\sysname{} is bootstrapped from an existing \commonlisp{}
implementation that, in addition to the functionality required by the
standard, also contains the library \texttt{closer-mop}.  This
\commonlisp{} system is called the \emph{host}.  The result of the
bootstrapping process is an \emph{image} in the form of an executable
file containing a \sysname{} system.  This system is called the
\emph{target}.  We have not yet decided whether to generate a complete
target system using the host, or whether to generate a partial system
that would then load additional functionality from compiled files.  At
the very least, the generated image must be \emph{viable}, meaning
that it is possible to obtain a complete \commonlisp{} system by
starting with that image and loading a sequence of ordinary compiled
files.

In general, the target image can be thought of as containing
\emph{graph} of \commonlisp{} objects that have been placed in memory
according to the spaces managed by the memory manager.  To create this
graph, we first generate an \emph{isomorphic} graph of host objects in
the memory of an executing host system.  To generate the target image,
the isomorphic host graph is traversed, creating a target version of
each object in the host graph, and placing that object on an
appropriate address in the target image.

The isomorphic host graph contains objects that are \emph{analogous}
to their target counterparts as follows:

\begin{itemize}
\item A target \texttt{fixnum} is represented as a host integer.
  Whether the integer is a host fixnum or not depends on the fixnum
  range of the host.
\item A target \texttt{character} is represented as a host character.
\item A target \texttt{cons} cell is represented as a host
  \texttt{cons} cell.
\item A target \texttt{symbol} is represented as a host symbol.
  Target symbols in the packages {\sc common-lisp} and {\sc keyword}
  are represented as the identical host symbols.  Target symbols in
  other packages are represented as uninterned host symbols.
\item A target standard object is represented as a host
  \texttt{standard-object} for the \emph{header} and a host
  \texttt{simple-vector} for the \emph{rack}.
\item Target objects such as bignums or floats are not needed at this
  stage of bootstrapping, so they do not have any representation as
  host objects.
\end{itemize}

\section{Global environments for bootstrapping}

During different phases of bootstrapping, a particular \emph{name} (of
a function, class, etc) must be associated with different objects.  As
a trivial example, the function \texttt{allocate-instance} in the host
system is used to allocate all standard objects.  But
\texttt{allocate-instance} is also a target function for allocating
objects according to the way such objects are represented by the
target system.  These two functions must be available simultaneously.

Most systems solve this problem by using temporary names for target
packages during the bootstrapping process.  For example, even though
in the final target system, the name \texttt{allocate-instance} must be
a symbol in the \texttt{common-lisp} package, during the bootstrapping
process, the name might be a symbol in a package with a different
name.

In \sysname{} we solve the problem by using multiple \emph{first-class
  global environments}, provided by the library Clostrum as described
in \refSec{sec-first-class-global-environments}.

For the purpose of bootstrapping, it is convenient to think of
\texttt{eval} as consisting of two distinct operations:

\begin{itemize}
\item Compile.  A \emph{compilation environment} is used to expand
  macros and for other compilation purposes.  The result of
  compilation is code that is \emph{untied} to any particular
  environment.
\item Tie.  The untied code produced by the first step is \emph{tied}
  to a particular run-time environment.  Tying is accomplished by
  calling the top-level function created by the compilation.
\end{itemize}

How tying a code object to a particular environment is accomplished in
the native system is described in detail in
\refChap{chap-tying-a-code-object}.  Tying a code object must also be
possible during bootstrapping, and how this is accomplished is
described in \refSec{sec-tying-a-code-object-during-bootstrapping}.

\section{Loading code into an environment}

During each bootstrapping phase, several files containing \sysname{}
source code are \emph{loaded} into a particular global environment.
Loading is always accomplished by a call to the function
\texttt{sicl-boot:load-source-file}.  This function has two
parameters.  The first parameter is a \emph{relative pathname} which
is a string that designates a pathname relative to the ASDF system
definition \texttt{sicl}.  The second parameter is a global
environment into which the code is to be loaded.  Loading a file means
evaluating the top-level forms in the file according to the semantics
of \commonlisp{}.

The function \texttt{sicl-boot:load-source-file} starts by converting
the relative pathname into an absolute pathname.  Then it loops until
the end of file of the input file, and for each iteration, it reads a
top-level form as a \emph{concrete syntax tree} or CST.  Finally, it
calls \texttt{cleavir-cst-to-ast:cst-eval} to evaluate the resulting
CST.

A method on \texttt{cleavir-cst-to-ast:cst-eval} specialized to the
\texttt{sicl-boot:client} class calls
\texttt{cleavir-cst-to-ast:cst-to-ast} and then it looks up the
function named \texttt{ast-eval} in the environment passed as an
argument, in order to evaluate the resulting AST.  In other words,
the effect of loading a file into an environment depends on the
definition in that environment of the function
\texttt{sicl-boot:ast-eval}.

In environments $e_0$, $e_2$, $e_3$, and $e_4$, the function
\texttt{sicl-boot:ast-eval} is defined to call the
\texttt{sicl-ast-evaluator:eval-ast}.  This function translates the
AST to host code in a way that all references to functions and
variables are relative to the environment in question.  It then
compiles that code using the host compiler, and finally it calls the
host function resulting from the compilation.  This AST evaluator is
fast, but it does not produce intermediate code, so it can not be used
to create target native instructions.  Instead, it is used in
environments where we need to only \emph{evaluate} the code.

In environment $e_5$, on the other hand, \texttt{sicl-boot:ast-eval}
is defined to call the HIR evaluator instead.  The way it does this,
is that it first translates the AST to a code object containing HIR
code.  It then calls the function
\texttt{sicl-compiler:tied-code-object} to tie the code object to the
environment.  This call results in the HIR code being translated to a
graph of \emph{thunks}, where each thunk is a host function that, when
called executes the effect of a single HIR instruction.

\section{Tying a code-object during bootstrapping}
\label{sec-tying-a-code-object-during-bootstrapping}

Bootstrapping must ultimately produce environment contents that is
analogous to that of the native system.  In particular, the HIR
evaluator must be able to produce the same effect as the execution of
the top-level function of a native code object, as described in
\refChap{chap-tying-a-code-object}.  In this section, we describe how
tying by the HIR evaluator is accomplished.

Recall that the following three actions must be accomplished:

\begin{enumerate}
\item References to named global functions must be resolved by the
  creation of a \emph{trampoline snippet} and the modification of the
  unconditional \emph{jump} instruction representing the call.
\item Load-time actions must be performed, but the top-level function
  in the form of HIR-evaluator chunks can accomplish these actions.
\item References to literals computed as part of the previous step must
  be resolved by the code vector being modified to refer to these
  literals.
\end{enumerate}

The first action is accomplished in the same way as with native code.
The main difficulty lies in the third action, and it occurs because a
computed literal may be referred to by subsequent code in the
top-level function.

To solve this difficulty, we introduce a HIR instruction
\texttt{load-literal}.  For a literal that is present in source code,
it would be possible for the instruction itself to contain a slot
holding the literal.  The HIR evaluator would then extract the value
of the slot and close over that value in the generated thunk.  The
code generator wold also extract this value and insert it into the
instruction stream as an immediate datum.  However, for a literal that
is computed by the top-level function, this solution is not possible.
The reason is that the \texttt{load-literal} instruction would then
have to be modified as a result of executing the top-level function.
But at this point, a HIR thunk has already been built from the
\texttt{load-literal} instruction.  HIR thunks must not close over
instructions, because instructions are subsequently modified when HIR
is turned into MIR, LIR, etc.

We solve this conundrum by introducing an indirection in the form of a
\texttt{cons} cell.  This cell is the value of a slot in the
\texttt{load-literal} instruction.  The HIR thunk generated from the
\texttt{load-literal} closes over this cell, and the execution of the
HIR thunk consists of accessing the \texttt{car} of this call and
write it to the output of the instruction.  We also introduce a HIR
instruction \texttt{patch-literal} that will turn into a named call to
\texttt{resolve-load-time-value} described in
\refChap{chap-tying-a-code-object} by the code generator.  The
\texttt{patch-literal} instruction takes three inputs, namely:

\begin{enumerate}
\item the literal object created from the load-time action,
\item an index into the code vector where the immediate object that
  the load-time action generates must be stored, and
\item an index into the vector of literals where the immediate that
  the load-time action generates must be stored for the benefit of
  the garbage collector.
\end{enumerate}

The \texttt{patch-literal} instruction also contains a \texttt{cons}
cell that is also contained in the \texttt{load-literal} instruction.

The HIR thunk generated from the \texttt{patch-literal} instruction
closes over the \texttt{cons} cell.  The actions of the HIR thunk are:

\begin{enumerate}
\item Store the first input in the \texttt{car} of the first
  \texttt{cons} cell.
\item Store the first input in the code vector, at the index indicated
  by the second input.  The code vector is the value of the special
  variable \texttt{*code-vector*} just as described in
  \refChap{chap-tying-a-code-object}.
\item Store the first input in the vector of literals at the index
  indicated by the third input.  The vector of literals is the value
  of the special variable \texttt{*literal-vector*} just as described
  in \refChap{chap-tying-a-code-object}.
\end{enumerate}

The second and the third inputs of the \texttt{patch-literal}
instruction are the outputs of \texttt{load-literal} instructions that
contain fixnums.  Some of these fixnums might be so small that they
could be represented as immediate inputs to the instruction, but this
code is executed only at load time, so performance is not a major
issue. 

\section{External libraries}

Most of the code in \sysname{} is supplied by external libraries.
These libraries require some existing functionality in order to work
properly, and this functionality must be supplied by the bootstrapping
procedure before the library is loaded.  If there are mutual
dependencies between libraries, we need to resolve these dependencies
temporarily during bootstrapping.  In this section, we enumerate the
external libraries \sysname{} depends on, and the functionality that
each one requires.  We list only functionality above and beyond what
host code can easily supply, such as functions on \texttt{cons}es and
similar.  The dependencies will determine the best order in which to
load these libraries, so as to minimize temporary bootstrapping code.

\subsection{Acclimation}

\subsubsection{Description}

Acclimation is a small library that is mainly used for
internationalized condition reporting.

\subsubsection{Dependencies}

Acclimation requires functionality for defining classes and generic
functions.  It also invokes the macro \texttt{define-condition} to
create a condition type.  One way to satisfy this dependency is to
depend on the system Predicament (\seesec{sec-predicament}).

\subsection{SICL-conditions}
\label{sec-sicl-conditions}

\subsubsection{Description}

SICL-conditions is a small system that defines the classes
\texttt{condition-class} (which is the metaclass for all condition
classes) and \texttt{condition} (which is a superclass of all
condition classes).  It also defines methods on
\texttt{reader-method-class} (that returns the class
\texttt{standard-reader-method}) and \texttt{writer-method-class}
(that returns the class \texttt{standard-writer-method}).  The home
package of the last four symbols is \texttt{clostrophilia}.

This system is a requirement for the system Predicament
(\seesec{sec-predicament}), because Predicament does not define the
metaclass for condition classes, nor the superclass for all condition
classes.

\subsubsection{Dependencies}

SICL-conditions requires the package \texttt{clostrophilia} to
exist. It also requires the ability to create classes and generic
functions.

\subsection{Predicament}
\label{sec-predicament}

\subsubsection{Description}

Predicament is an implementation of the \commonlisp{} condition system.

\subsubsection{Dependencies}

Predicament depends on SICL-conditions (seesec{sec-sicl-conditions}).
The reason is that Predicament does not define the class
\texttt{condition} not its metaclass, which in \sysname{} is
\texttt{sicl-condition:condition-class}.  It also does not define the
macro \texttt{define-condition} because the expansion of that macro
must mention the metaclass of the condition classes.

Furthermore, Predicament defines methods on \texttt{error},
\texttt{warning}, and \texttt{signal}, specialized to the class
\texttt{string}, so that class must exist in the environment into
which Predicament is loaded.  In early stages of bootstrapping, this
class can be imported from the host, because it is likely that an
argument of type string to one of these functions will be a literal
string in the source code, in which case the reader returns a host
string.

Predicament also refers to two special variables, namely
\texttt{*error-output*} and \texttt{*query-io*}.  These are used only
at run time, so they just have to be defined during bootstrapping.
The simplest solution is to import them from the host.

The macro \texttt{restart-case} calls three functions at
macroexpansion time, namely \texttt{restart-case-make-report-subform},
\texttt{restart-case-make-interactive-subform}, and
\texttt{restart-case-make-test-subform}.  Each of these functions
contains a \texttt{typecase} form that expands to a call to
\texttt{typep}.  The types tested for are \texttt{null} and
\texttt{string}.  Predicament could have used predicates \texttt{null}
and \texttt{stringp} instead, but that is not currently the case.  And
\texttt{restart-case} is used (directly or indirectly) in the
definitions of the functions \texttt{cerror}, \texttt{break} and
\texttt{warn}.  As a result, some version of \texttt{typep} must exist
when Predicament is loaded.  It must also exist when
\texttt{restart-case} is used in subsequently loaded systems, but its
use is relatively rare.  So one solution is to define a special
version of \texttt{typep} that can handle \texttt{null} and
\texttt{string} for the duration of the loading of Predicament.

Finally, Predicament calls \texttt{macroexpand} as part of the
\texttt{restart-case} macro, in order to determine whether the
signaling form is one of \texttt{signal}, \texttt{warn},
\texttt{error}, or \texttt{cerror}.  Since the signaling form could be
a macro form that expands to one of these, Predicament calls
\texttt{macroexpand}.  The relevant phrase in the standard that
supports this behavior is: ``If the restartable-form is a list whose
car is any of the symbols signal, error, cerror, or warn (or is a
macro form which macroexpands into such a list), then
with-condition-restarts is used implicitly to associate the indicated
restarts with the condition to be signaled.''

\subsubsection{Conclusions}

Predicament has a few dependencies, but they are not very hard to
satisfy.  Furthermore, Predicament provides functionality that is used
by several other systems, in particular the macros
\texttt{define-condition}, \texttt{handler-case}, and
\texttt{handler-bind}.  It therefore seems desirable to load
Predicament early in the bootstrapping procedure.

\subsection{Clostrophilia class hierarchy}
\label{clostrophilia-class-hierarchy}

\subsubsection{Description}

This system provides the MOP class hierarchy as documented in the AMOP
book.

\subsubsection{Dependencies}

This system depends on the ability to create generic functions and
methods (for the slot accessors) and also classes.  In the first phase
of bootstrapping, the host functionality for these abilities is used.
In subsequent phases, when this system is loaded into some environment
$E_i$, it depends on several systems to be loaded into $E_{i-1}$,
namely:

\begin{itemize}
\item Clostrophilia generic-function initialization.
\item Clostrophilia class initialization.
\item Clostrophilia method initialization.
\item Clostrophilia slot initialization.
\end{itemize}

\subsubsection{Conclusions}

This system can be loaded very early in each phase, and it is needed
in order for other systems to use the classes and the slot accessors
that this system provides.

\subsection{Clostrophilia standard-object initialization}

\subsubsection{Description}

This system provides definitions of the initialization generic
functions \texttt{initialize-instance},
\texttt{reinitialize-instance}, and \texttt{shared-initialize}.

This system is not needed in phase 1 of bootstrapping, because the
objects created in phase 1 are host objects instantiated from host
classes, so the host functions for standard-object initialization are
used in phase 1.

In subsequent phases, this system is needed in some environment $E_i$
in order to create instances of classes defined in $E_i$, but not to
define objects in $E_i$.

\subsubsection{Dependencies}

\subsubsection{Conclusions}

\subsection{\texttt{typep}}

\subsubsection{Description}

\begin{itemize}
\item \texttt{class}.  The function \texttt{ensure-class-using-class}
  in the system \texttt{sicl-ensure-metaobject-using} calls
  \texttt{typep} to check whether a \emph{superclass} argument is a
  class metaobject, a symbol, or something else.  If it is a symbol,
  it turns it into a class by using \texttt{find-class}.  The system
  Clostrophilia class initialization uses \texttt{typep} to check that
  each superclass in the list of superclasses is a class metaobject,
  and calls \texttt{error} otherwise.
\item \texttt{method-combination}.  The system Clostrophilia
  generic-function initialization calls \texttt{typep} to check
  whether the object given is a method combination metaobject, and if
  not, calls \texttt{error}.
\end{itemize}



\subsubsection{Dependencies}

\subsubsection{Conclusions}

\subsection{ctype}
\label{sec-subtype}

\subsubsection{Description}

This system is a complete implementation of the \commonlisp{} type
system, and in particular it provides implementations of the standard
functions \texttt{typep} and \texttt{subtypep}.

\subsubsection{Dependencies}

This system requires the ability to define generic functions, method,
and standard classes.  It also requires
\texttt{define-method-combination} because it uses a custom method
combination for many of its generic functions.

When \texttt{ctype} is configured for \sysname{}, it also requires the
existence of all standardized system classes.  During bootstrapping,
many of these classes can be created with no slots and be redefined
later.  This is especially true for classes that are not otherwise
used during bootstrapping, such as \texttt{random-state} and
\texttt{readtable}.

At the end of the procedure of loading \texttt{ctype}, it creates
instances of the classes that it defines.  The very purpose if the
code loaded into some environment $E_i$ is to make it possible to
create instances of the classes defined in $E_i$, in particular
instances of \texttt{generic-function} and of \texttt{class}, but also
of other classes.  Therefore, before any instances of classes defined
in $E_i$ can be created, the machinery for allocating and initializing
objects must have already been loaded.  This machinery consists of
\texttt{allocate-instance}, \texttt{make-instance},
\texttt{initialize-instance}, and \texttt{shared-initialize}.  So the
code for this machinery must be loaded before \texttt{ctype} can be
loaded.  In phase 1, this machinery is provided by the host, so it
suffices to make sure that the host version of \texttt{make-instance}
is.  In subsequent phases, the code for this machinery must be loaded
before \texttt{ctype} can be loaded.

\subsubsection{Conclusions}

The \texttt{ctype} library must be loaded very late in each phase.

\subsection{Regalia}
\label{sec-regalia}

\subsubsection{Description}

\subsubsection{Dependencies}

\section{Bootstrapping phases}

\subsection{Definitions}

\begin{definition}
A \emph{simple instance} is an instance of some class, but that is
also neither a class nor a generic function.
\end{definition}

\begin{definition}
A \emph{host class} is a class in the host system.  If it is an
instance of the host class \texttt{standard-class}, then it is
typically created by the host macro \texttt{defclass}.
\end{definition}

\begin{definition}
A \emph{host instance} is an instance of a host class.  If it is an
instance of the host class \texttt{standard-object}, then it is
typically created by a call to the host function
\texttt{make-instance} using a host class or the name of a host class.
\end{definition}

\begin{definition}
A \emph{host generic function} is a generic function created by the
host macro \texttt{defgeneric}, so it is a host instance of the host
class \texttt{generic-function}.  Arguments to the discriminating
function of such a generic function are host instances.  The host
function \texttt{class-of} is called on some required arguments in
order to determine what methods to call.
\end{definition}

\begin{definition}
A \emph{host method} is a method created by the host macro
\texttt{defmethod}, so it is a host instance of the host class
\texttt{method}.  The class specializers of such a method are host
classes.
\end{definition}

\begin{definition}
A \emph{simple host instance} is a host instance that is neither a
host class nor a host generic function.
\end{definition}

\begin{definition}
An \emph{ersatz instance} is a target instance represented as a host
data structure, using a host standard object to represent the
\emph{header} and a host simple vector to represent the \emph{rack}.
In fact, the header is an instance of the host class
\texttt{funcallable-standard-object} so that some ersatz instances can
be used as functions in the host system.
\end{definition}

\begin{definition}
An ersatz instance is said to be \emph{pure} if the class slot of the
header is also an ersatz instance.  An ersatz instance is said to be
\emph{impure} if it is not pure.  See below for more information on
impure ersatz instances.
\end{definition}

\begin{definition}
An \emph{ersatz class} is an ersatz instance that can be instantiated
to obtain another ersatz instance.
\end{definition}

\begin{definition}
An \emph{ersatz generic function} is an ersatz instance that is also a
generic function.  It is possible for an ersatz generic function be
executed in the host system because the header object is an instance
of the host class \texttt{funcallable-standard-object}.  The methods
on an ersatz generic function are ersatz methods.
\end{definition}

\begin{definition}
An \emph{ersatz method} is an ersatz instance that is also a method.
\end{definition}

\begin{definition}
A \emph{bridge class} is a representation of a target class as a
simple host instance.  An impure ersatz instance has a bridge class in
the class slot of its header.  A bridge class can be instantiated to
obtain an impure ersatz instance.
\end{definition}

\begin{definition}
A \emph{bridge generic function} is a target generic function
represented as a simple host instance, though it is an instance of the
host function \texttt{funcallable-standard-object} so it can be
executed by the host.

Arguments to a bridge generic function are ersatz instances.  The
bridge generic function uses the
\emph{stamp}
\seesec{sec-generic-function-dispatch-the-discriminating-function} of
the required arguments to dispatch on.

The methods on a bridge generic function are bridge methods.
\end{definition}

\begin{definition}
A \emph{bridge method} is a target method represented by a simple host
instance.  The class specializers of such a method are bridge classes.
The \emph{method function} of a bridge method is an ordinary host
function.
\end{definition}

\subsection{Preparation}

In addition to the host environment, four different Clostrum
environments are involved in the bootstrapping procedure.
We shall refer to them as $E_1$, $E_2$, $E_3$, and $E_4$.

Each environment is an instance of (often a subclass of) a class
\texttt{environment} defined in the \texttt{sicl-boot} package.  As
such, when created, each environment is automatically filled with
several definitions such as:

\begin{itemize}
\item standard special operators,
\item host functions for a variety of purposes,
\item etc.
\end{itemize}

When code is loaded into one of the environments, the behavior of some
important operators depends on the environment in question as follows:

\subsubsection{Environment $E_1$}

\begin{itemize}
\item \texttt{make-instance} creates an instance of a class in $E_1$.
  We accomplish this effect by defining a special bootstrapping
  version of \texttt{make-instance}.  When given a symbol as its first
  argument, this special version looks up the class in $E_1$ and calls
  the host version of \texttt{make-instance}, passing that class as
  the first argument.  Put differently, \texttt{make-instance} in
  $E_1$ creates a \emph{bridge object}.
\item \texttt{defgeneric} creates an instance of the host class
  \texttt{standard-generic-function} and binds its name to the
  resulting object in $E_1$.  We accomplish this effect by a method on
  \texttt{common-macro-definitions:ensure-generic-function}.  This
  method is meant to provide an expansion that contains
  \texttt{ensure-generic-function}, but we create the generic function
  at macro-expansion time.  The generic function is created by a call
  to the host function \texttt{make-instance}, and the result is then
  associated with the name in $E_1$.
\item \texttt{defmethod} creates an instance of the host class
  \texttt{standard-method} and adds it to the named generic function
  in $E_1$.  For \texttt{defmethod} we can not create the method at
  macro-expansion time, because the \texttt{defmethod} form can occur
  in a non-null lexical environment.  So we must create a working
  expansion that can then be compiled in the appropriate lexical
  environment.  The system Common Macro Definitions requires us to
  define a method on \texttt{wrap-in-make-method-lambda} and on
  \texttt{wrap-in-ensure-method}.  For
  \texttt{wrap-in-make-method-lambda}, we are given a lambda
  expression representing the body of the method, and the expansion
  should be that body wrapped in the macro form
  \texttt{make-method-lambda} defined by the MOP.  However,
  \texttt{make-method-lambda} is not available on all platforms, and
  we can assume that the default action is what is required.  The
  default action for a standard method is to wrap the lambda
  expression in a lambda expression that has two required parameters,
  namely the list of arguments to the method, and a list of next
  methods to be executed as a result of a call to
  \texttt{call-next-method}.  Furthermore, the wrapper should contain
  definitions of \texttt{next-method-p} and \texttt{call-next-method}.
  We accomplish this with a \texttt{flet} expression defining these
  local functions.  For \texttt{wrap-in-ensure-method}, we wrap the
  method function in a form calling a special bootstrapping-version of
  \texttt{ensure-method}.  This special version creates the method by
  calling the host function \texttt{make-instance} with the class name
  \texttt{standard-method} and then calling the host function
  \texttt{add-method} to add the method to the generic function.
\item \texttt{defclass} creates an instance of the host class
  \texttt{funcallable-standard-class} and binds it to a name in $E_1$.
  The system Common Macro Definitions requires us to supply a method
  on \texttt{ensure-class-name}, and we supply the name
  \texttt{ensure-class} in the boot package.  We define the
  bootstrapping-specific function to call the host function
  \texttt{make-instance}, but there are some complications due to the
  way class initialization is defined in the MOP.  The problem is that
  \texttt{ensure-class} is defined to call
  \texttt{ensure-class-using-class} which calls \texttt{make-instance}
  without first processing the slot specifications.  Such a slot
  specification contains a list of function names to be used as slot
  readers and a list of function names to be used as slot writers.  If
  we were to include these canonical slot specifications in the call
  to the host function \texttt{make-instance} then the
  class-initialization protocol of the host would create host generic
  functions with names in the host global environment corresponding to
  these readers and writers, and we clearly do not want that.  So we
  need to do two things: First, we need to remove those slot options
  before calling host \texttt{make-instance}, and second, we must then
  add those reader and writer methods to the generic functions being
  named, and create those functions in case they do not exist.
\item \texttt{defun} creates a host function FIXME: SAY MORE.
\item \texttt{define-method-combination} creates a host method
  combination, accomplished by a call to host \texttt{eval}.  In phase
  1, only custom method-combination types are defined so their names
  are translated by the combination Eclector and the extrinsic Parcl
  system to host uninterned symbols.
\end{itemize}

\subsubsection{Environment $E_2$}

\subsubsection{Environment $E_3$}

\subsubsection{Environment $E_4$}

\subsection{Phase 1}

In phase $1$, we load enough functionality into environment $E0$ to be
able to produce abstract syntax trees (ASTs) from source files.  This
functionality involves mainly standard macros that are required during
compilation.

We start by defining the macro \texttt{defmacro} \emph{manually}, but
the version defined this way is incorrect, because it uses the host
compiler to compile the body of defined macros in the null lexical
environment.  However, it is good enough to load definitions of
a few additional macros required before the production version of
\texttt{defmacro} can be loaded.

Additional functions are then imported from the host, in particular
expander functions for conditional macros and functions for parsing
macro bodies.

Then, definitions of additional standard macros are loaded in a well
defined order.  Initially, macros required to define \texttt{defmacro}
are loaded, so that a pure \sysname{} version of \texttt{defmacro} can
be loaded.  In particular, \texttt{lambda} and \texttt{setf} are
needed.  This sequence ends with two subsequent load of the \sysname{}
definition of \texttt{defmacro} in order to have a version of it with
the macro function compiled by the \sysname{} compiler.

Once a \sysname{} version of \texttt{defmacro} is available, files
containing definitions of most standard macros are loaded.  The result
is an environment $e_0$ with a fairly complete set of standard
macros.

\subsection{Phase 2}

We define a class named
\texttt{sicl-boot-phase-2:funcallable-standard-class} in the host
environment.  It is defined as a direct subclass of the host class
\texttt{closer-mop:funcallable-standard-class}.  When we
evaluate \texttt{defclass} forms in phase 3, the classes created are
instances of this class.  We could have chosen this class only for
instances that need to be executable in the host, and a subclass of
the host class \texttt{standard-class} for the others, but the host
class \texttt{funcallable-standard-class} can do everything that the
host class named \texttt{standard-class} can, so we simplify the code by
using one single class.

We define an \texttt{:around} method on \texttt{initialize-instance}
in the host environment, specialized to
\texttt{sicl-boot-phase-2:funcallable-standard-class}.  The purpose of
this \texttt{:around} method is to remove the \texttt{:reader} and
\texttt{:accessor} slot options supplied in the \texttt{defclass}
forms that we evaluate in phase 2.  Without this \texttt{:around}
method, the host function \texttt{initialize-instance} would receive
keyword arguments \texttt{:readers} and \texttt{:writers} and it would
then add methods to host generic functions corresponding to the names
given.  Instead, this \texttt{:around} method adds the readers and
writers to the generic function with the corresponding name in
envirnoment $E_3$.  It assumes that this generic function exists, so
we must create it explicitly before a class that defines the accessor
method can be defined.

In environment $E_1$, we define the following classes:

\begin{itemize}
\item \texttt{t}.  This class is the same as the host class
  \texttt{t}.  It will be used as a specializer on method arguments
  that are not otherwise specialized.
\item \texttt{common-lisp:standard-generic-function}.  This class is
  the same as the class with the same name in the host environment.
  It will be used to create host generic functions in environment
  $E_2$.
\item \texttt{common-lisp:standard-method}.  This class is
  the same as the class with the same name in the host environment.
  This class will be used to create methods on the generic functions
  that we create in environment $E_3$.
\item \texttt{common-lisp:standard-class}.  This class is the same as
  the class named
  \texttt{sicl-boot-phase-1:funcallable-standard-class} in the host
  environment.  It will be used to create most classes in $E_2$.
\item \texttt{common-lisp:built-in-class}.  This class is the same as
  the class named
  \texttt{sicl-boot-phase-1:funcallable-standard-class} in the host
  environment.  It will be used to create some classes in $E_2$, for
  example \texttt{t} and \texttt{function}.
\item \texttt{sicl-clos:funcallable-standard-class}.  This class is
  the same as the class named
  \texttt{sicl-boot-phase-1:funcallable-standard-class} in the host
  environment.  It will be used to create some classes in $E_2$, such
  as \texttt{generic-function} and \texttt{standard-generic-function}.
\item \texttt{sicl-clos:standard-direct-slot-definition}.  This class
  is the same as the class named
  \texttt{closer-mop:standard-direct-slot-definition} in the host
  environment.  This class will be used to create slot-definition
  metaobjects for the classes that we create in environment $E_2$.
\end{itemize}

\subsection{Phase 2}

The purpose of phase~2 is:

\begin{itemize}
\item to create host generic functions in $E_3$ corresponding to all
  the accessor functions defined by \sysname{} on standard MOP
  classes, and
\item to create a hierarchy in $E_2$ of host standard classes that has
  the same structure as the hierarchy of MOP classes.
\end{itemize}


Three different environments are involved in phase~2:

\begin{itemize}
\item Environment $E_1$ is used to find find host classes to
  instantiate.  The class named \texttt{standard-class} in $E_1$ is
  used to instantiate most of the classes in environment $E_2$, for
  example, \texttt{standard-class}, \texttt{built-in-class},
  \texttt{slot-definition}, etc.  The class named
  \texttt{built-in-class} in $E_1$ is used to create classes
  \texttt{t} and \texttt{function} as well as some non-MOP classes in
  $E_2$.  The class named \texttt{funcallable-standard-class} in $E_1$
  is used to create classes \texttt{generic-function} and
  \texttt{standard-generic-function}, also in environment $E_2$.  The
  class named \texttt{standard-direct-slot-definition} in $E_1$ is
  used to define slot-definition metaobjects for the classes in
  environment $E_2$.  Environment $E_1$ is also used to find host
  classes \texttt{standard-generic-function} and
  \texttt{standard-method} to instantiate in order to create generic
  functions in environment $E_3$ as well as methods on those generic
  functions.
\item The run-time environment $E_2$ is where instances of the host
  classes named \texttt{standard-class},
  \texttt{funcallable-standard-class}, and \texttt{built-in-class} in
  environment $E_1$ will be associated with the names of the MOP
  hierarchy of classes.  These instances are thus host classes.  The
  entire MOP hierarchy is created as are some built-in classes such as
  \texttt{cons} and some of the number classes.
\item The run-time environment $E_3$ is where instances of the host
  class named \texttt{standard-generic-function} will be associated
  with the names of the different accessors specialized to host
  classes created in $E_2$.
\end{itemize}

One might ask at this point why generic functions are not defined in
the same environment as classes.  The simple answer is that there are
some generic functions that were automatically imported into $E_2$
from the host, that we still need in $E_2$, and that would have been
overwritten by new ones if we had defined new generic functions in
$E_2$.

Several adaptations are necessary in order to accomplish phase~2:

\begin{itemize}
\item A special version of the function
  \texttt{ensure-generic-function} is defined in environment $E_3$.
  It checks whether there is already a function with the name passed
  as an argument in $E_3$, and if so, it returns that function.  It
  makes no verification that such an existing function is really a
  generic function; it assumes that it is.  It also assumes that the
  parameters of that generic function correspond to the arguments of
  \texttt{ensure-generic-function}.  If there is no generic function
  with the name passed as an argument in $E_3$, it creates an instance
  of the host class \texttt{standard-generic-function} and associate
  it with the name in $E_3$.  To create such an instance, it calls the
  host function \texttt{make-instance}.
\item The function \texttt{ensure-class} has a special version in
  $E_2$.  Rather than checking for an existing class, it always
  creates a new one.
\end{itemize}

Phase~2 is divided into two steps:

\begin{enumerate}
\item First, the \texttt{defgeneric} forms corresponding to the
  accessors of the classes of the MOP hierarchy are evaluated using
  $E_2$ as both the compilation environment and run-time environment.
  The result of this step is a set of host generic functions in $E_3$,
  each having no methods.
\item Next, the \texttt{defclass} forms corresponding to the classes
  of the MOP hierarchy are evaluated using $E_2$ as both the
  compilation environment and run-time environment.  The result of
  this step is a set of host classes in $E_2$ and host standard
  methods on the accessor generic functions created in step~1
  specialized to these classes.
\end{enumerate}

\subsection{Phase 3}

The purpose of phase~3 is to create a hierarchy of bridge classes that
has the same structure as the hierarchy of MOP classes.

Three different environments are involved in phase~3:

\begin{itemize}
\item The run-time environment $E_2$ is used to look up metaclasses to
  instantiate in order to create the bridge classes.
\item The run-time environment $E_3$ is the one in which bridge
  classes will be associated with names.
\item The run-time environment $E_4$ is the one in which bridge
  generic functions will be associated with names.
\end{itemize}

We start by creating generic functions corresponding to all slot
accessors that are defined in the MOP hierarchy.  We then create
bridge classes corresponding to the classes of the MOP hierarchy.
When a bridge class is created, it will automatically create bridge
methods on the bridge generic functions corresponding to slot readers
and writers.

Creating bridge classes this way will also instantiate the host class
\texttt{target:direct-slot-definition}.

In this phase, we also prepare for the creation of ersatz instances.

\subsection{Phase 4}

The purpose of this phase is to create ersatz generic functions and
ersatz classes, by instantiating bridge classes. 

At the end of this phase, we have a set of ersatz instances, some of
which are ersatz classes, except that the \texttt{class} slot of the
header object of every such instance is a bridge class.  We call such
ersatz instances \emph{impure}.  We also have a set of ersatz generic
functions (mainly accessors) that are ersatz instances like all the
others.

\subsection{Phase 5}

The first step of this phase is to finalize all the ersatz classes
that were created in phase 4.  Finalization will create ersatz
instances of bridge classes corresponding to effective slot
definitions.

The second step repeats the creation of MOP generic functions and MOP
classes, this time in environments $E_6$ and $E_5$ respectively.  As
opposed to the objects created in phase~4, the objects created in this
phase are \emph{pure} ersatz objects, in that the class slot of the
header object is also an ersatz object, albeit impure.

\subsection{Phase 6}

\subsection{Phase 7}

The purpose of this phase is to create ersatz instances for all
objects that are needed in order to obtain a viable image, including:

\begin{itemize}
\item ersatz built-in classes such as \texttt{package}, \texttt{symbol},
  \texttt{string}, etc.,
\item ersatz instances of those classes, such as the required
  packages, the symbols contained in those packages, the names of
  those symbols, etc.
\item ersatz standard classes for representing the global environment
  and its contents.
\item ersatz instances of those classes.
\end{itemize}

\subsection{Phase 8}

The purpose of this phase is to replace all the host instances that
have been used so far as part of the entire ersatz structure, such as
symbols, lists, and integers by their ersatz counterparts.

\subsection{Phase 9}

The purpose of this phase is to take the simulated graph of objects
used so far and transfer it to a \emph{memory image}. 

\subsection{Phase 10}

Finally, the memory image is written to a binary file.

% LocalWords:  Clostrophilia accessors
